Motion Estimation is one of the most computationally complex processes within a video encoding system. This is especially true for an ITU-T H.264/ISO MPEG-4 AVC based encoder considering that motion estimation may need to be performed using multiple references or block sizes. With the extension and usage however of the H.264 standard into higher resolutions and formats, encoding speed has become even more vital.
The basic idea of motion estimation is to look for portions of a “current” frame (during the process of coding a stream of digital video frames for transmission and the like) that are the same or nearly the same as portions of previous frames, albeit, in different positions on the frame because the subject of the frame has moved. If such a block of basically redundant pixels is found in a preceding frame, the system need only transmit a code that tells the reconstruction end of the system where to find the needed pixels in a previously received frame.
Thus motion estimation is the task of finding predictive blocks of image samples (pixels) within references images (reference frames, or just references) that best match a similar-sized block of samples (pixels) in the current image (frame). It is a key component of video coding technologies, and is one of the most computationally complex processes within a video encoding system. It is therefore highly desirable to consider fast motion estimation strategies so as to reduce encoding complexity while simultaneously having minimal impact on compression efficiency and quality.
In A. M. Tourapis, H. Y. Cheong, and P. Topiwala, “Fast ME in the JM reference software,” ISO/IEC JTC1/SC29/WG11 and ITU-T Q6/SG16, document JVT-P026, July '05, an extension of predictive based fast motion estimation algorithms was presented and named as the Enhanced Predictive Zonal Search schemes, which were later adopted and implemented into the JM reference software. Although the EPZS scheme can easily be extended to simultaneously consider fractional samples, the original implementation only considered integer samples. Nevertheless, and without adapting the original EPZS implementation to subpel positions but considering that subpixel motion estimation becomes the biggest bottleneck after the introduction of this scheme, a simple yet efficient fractional sample fast motion estimation scheme is introduced herein.